競プロ典型90問 068 Paired Information(★5)
まず,
$ T_i = 1
のクエリについて, 答えが一通りに定まるかどうかはUnion-Findで処理できる.
もし, 答えが一通りに定まる場合, 条件より答えが変化することはない. よって, クエリを先読みしておき, 全ての関係性が分かった状態で答えを求めることを考える. これは,
偶奇性
に注目し,
差分をとる
ことにより実装できる(各連結成分について, 始めの頂点が
$ 0
の場合の答えを考えればよい)
実装例:
https://atcoder.jp/contests/typical90/submissions/25345063